#include <iostream>
#include <vector>
using namespace std;

void Qsort(vector<int>& arr, int l, int r)
{
	if (l >= r) return;
	int key = arr[rand() % (r - l + 1) + l];
	int left = l - 1, right = r + 1;
	int i = l;
	while (i < right)
	{
		if (arr[i] < key) swap(arr[i++], arr[++left]);
		else if (arr[i] == key) ++i;
		else swap(arr[i], arr[--right]);
	}
	Qsort(arr, l, left);
	Qsort(arr, right, r);
}


int main()
{
	srand(time(0));
	vector<int> arr = { 4,3,5,6,8,0,9,8,7,1,2 };
	int n = arr.size();
	Qsort(arr, 0, n - 1);
	for (auto e : arr)
	{
		cout << e << " ";
	}
	return 0;
}